# -*- coding: utf-8 -*-

"""
    Time    : 2020/12/1 上午11:12
    Author  : Thinkgamer
    File    : 005-最长回文子串.py
    Software: PyCharm
    Desc    : https://leetcode-cn.com/problems/longest-palindromic-substring
"""

"""
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：
输入: "cbbd"
输出: "bb"
"""


# 超时
def longest_palindrome_v1(s):
	"""
	:type s: str
    :rtype: str
    """
	# 思路：遍历每一个元素，进行对称判断，对称有两种对称情况
	#   1：以当前元素为中心对称，即回文子串长度为奇数；
	#   2：以当前元素为对称元素中的一个，即回文子串长度为偶数
	start_index = 0
	max_len = 1
	for i in range(1, s.__len__()):
		j = 1
		while j <= i:
			# 以当前元素为对称轴（最大回文字串为奇数）
			if i + j < s.__len__() and s[i - j] == s[i + j]:
				if j * 2 + 1 > max_len:
					max_len = j * 2 + 1
					start_index = i - j
			else:
				break
			j += 1
			print("i: {}, j: {}, max_len: {}, start_index: {}".format(i, j, max_len, start_index))
			print(s[start_index:start_index + max_len])
		j = 1
		while j <= i:
			# 以当前元素为右侧的第一个对称元素（最大回文字串为偶数）
			if i + j - 1 < s.__len__() and s[i - j] == s[i + j - 1]:
				if j * 2 > max_len:
					max_len = j * 2
					start_index = i - j
			else:
				break
			j += 1
			print("i: {}, j: {}, max_len: {}, start_index: {}".format(i, j, max_len, start_index))
			print(s[start_index:start_index + max_len])
	print(s[start_index:start_index + max_len])
	return s[start_index:start_index + max_len]


# 1292 ms 66.25% / 13MB 65.99%
def longest_palindrome_v1_1(s):
	"""
	:type s: str
    :rtype: str
    """
	# 思路：遍历每一个元素，进行对称判断，对称有两种对称情况
	#   1：以当前元素为中心对称，即回文子串长度为奇数；
	#   2：以当前元素为对称元素中的一个，即回文子串长度为偶数 aacc
	start_index = 0
	max_len = 1
	for i in range(1, s.__len__()):
		j = 1
		while j <= i:
			# 以当前元素为对称轴（最大回文字串为奇数）
			if j * 2 + 1 > max_len and i + j < s.__len__() and s[i - j] == s[i + j]:
				max_len = j * 2 + 1
				start_index = i - j
			# 如果不满足条件 就 break，避免无谓的遍历
			if i + j >= s.__len__() or s[i - j] != s[i + j]:
				break
			j += 1
			# print("「1」i: {}, j: {}, max_len: {}, start_index: {}".format(i, j, max_len, start_index))
			# print(s[start_index:start_index + max_len])
		j = 1
		while j <= i:
			# 以当前元素为右侧的第一个对称元素（最大回文字串为偶数）
			if j * 2 > max_len and i + j - 1 < s.__len__() and s[i - j] == s[i + j - 1]:
				max_len = j * 2
				start_index = i - j
			# 如果不满足条件 就 break，避免无谓的遍历
			if i + j - 1 >= s.__len__() or s[i - j] != s[i + j - 1]:
				break
			j += 1
			# print("「2」i: {}, j: {}, max_len: {}, start_index: {}".format(i, j, max_len, start_index))
			# print(s[start_index:start_index + max_len])
	# print(s[start_index:start_index + max_len])
	return s[start_index:start_index + max_len]


# 超时
def longest_palindrome_v2(s):
	# 思路：遍历每一个元素，进行对称判断，对称有两种对称情况
	#   1：以当前元素为中心对称，即回文子串长度为奇数；
	#   2：以当前元素为对称元素中的一个，即回文子串长度为偶数
	start_index = 0
	max_len = 1
	for i in range(1, s.__len__()):
		# 标示是否继续使用 情况1 进行判断
		flag1 = True
		# 标示是否继续使用 情况2 进行判断
		flag2 = True
		j = 1
		while j <= i:
			# 1、以当前元素为对称轴（最大回文字串为奇数）
			if i + j < s.__len__() and s[i - j] == s[i + j] and flag1:
				if j * 2 + 1 > max_len:
					max_len = j * 2 + 1
					start_index = i - j
				if i+j-1 >= s.__len__() or s[i-j] != s[i+j-1]:
					flag2 = False
			# 2、以当前元素为右侧的第一个对称元素（最大回文字串为偶数）
			elif i + j - 1 < s.__len__() and s[i - j] == s[i + j - 1] and flag2:
				if j * 2 > max_len:
					max_len = j * 2
					start_index = i - j
				if i + j >= s.__len__() or s[i - j] != s[i + j]:
					flag1 = False
			else:
				break
			print("i: {}, j: {}, flag1: {}, flag2: {}, max_len: {}, start_index: {}".format(i, j, flag1, flag2, max_len, start_index))
			print(s[start_index:start_index + max_len])
			j += 1
	print(s[start_index:start_index + max_len])
	return s[start_index:start_index + max_len]


# 超时的原因：进行多次无谓的遍历
def longest_palindrome_v3(s):
	# 思路：遍历每一个元素，进行对称判断，对称有两种对称情况
	#   1：以当前元素为中心对称，即回文子串长度为奇数；
	#   2：以当前元素为对称元素中的一个，即回文子串长度为偶数
	start_index = 0
	max_len = 1
	for i in range(1, s.__len__()):
		flag1 = True
		flag2 = True
		j = 1
		while j <= i:
			# 以当前元素为对称轴（最大回文字串为奇数）
			if i + j < s.__len__() and s[i - j] == s[i + j] and flag1:
				if j * 2 + 1 > max_len:
					max_len = j * 2 + 1
					start_index = i - j
				if flag2 or i+j-1 >= s.__len__() or s[i-j] != s[i+j-1]:
					flag2 = False
			# 以当前元素为右侧的第一个对称元素（最大回文字串为偶数）
			elif i + j - 1 < s.__len__() and s[i - j] == s[i + j - 1] and flag2:
				if j * 2 > max_len:
					max_len = j * 2
					start_index = i - j
				if flag1 or i + j >= s.__len__() or s[i - j] != s[i + j]:
					flag1 = False
			else:
				break
			print("i: {}, j: {}, flag1: {}, flag2: {}, max_len: {}, start_index: {}".format(i, j, flag1, flag2, max_len, start_index))
			print(s[start_index:start_index + max_len])
			j += 1
	print(s[start_index:start_index + max_len])
	return s[start_index:start_index + max_len]


# 使用动态规划
# 9380 ms 5.78% | 22.4 MB  6.02%
def longest_palindrome_v4(s):
	result = ""
	n = len(s)
	dp = [[False] * n for _ in range(n)]
	# l + 1 表示的是回文子串的长度
	for l in range(n):
		# 枚举子串的起始位置 i，可以通过 i+l 获取子串的结束位置
		for i in range(n):
			# j 表示子串的结束位置
			j = i + l
			if j >= n:
				break
			# 回文子串的长度为1
			if l == 0:
				dp[i][j] = True
			# 回文子串的长度为2
			elif l == 1:
				dp[i][j] = (s[i] == s[j])
			else:
				dp[i][j] = dp[i+1][j-1] and s[i] == s[j]
			if dp[i][j] and l + 1 > len(result):
				result = s[i:j+1]
	print("最大回文子串为：{}".format(result))
	return result

"""
存在的特殊情况：ccc、aaaa、cc、aacc、aca、a、ac、aacabdkacaa、abbcccbbbcaaccbababcbcabca、aaaabaaa
s = "abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababa"
"""
# s = "aaaabaaa"
s = "abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababa"
# longest_palindrome_v1_1(s)
longest_palindrome_v4(s)

